Manual Big-O Analysis
Time: O(n^2) • Space: O(1)
Why: Nested loops detected → quadratic time. These are heuristics; empirical results below provide a practical check.
Time: O(2^n) • Space: O(n)
Why: Multiple recursive calls per invocation detected → exponential recursion tree. These are heuristics; empirical results below provide a practical check.
Time: O(2^n) • Space: O(n)
Why: Multiple recursive calls per invocation detected → exponential recursion tree. These are heuristics; empirical results below provide a practical check.
Time: O(n·W) • Space: O(n·W)
Why: DP array usage detected → table-filling DP complexity. These are heuristics; empirical results below provide a practical check.
Time: O(n·W) • Space: O(n·W)
Why: DP array usage detected → table-filling DP complexity. These are heuristics; empirical results below provide a practical check.
Performance Overview
Combined runtime, memory, and rank summary
Complexity Analysis
Heuristic Guess
Dynamic Guess
Heuristic Guess
Dynamic Guess
Heuristic Guess
Dynamic Guess
Heuristic Guess
Dynamic Guess
Heuristic Guess
Dynamic Guess
Runtime Chart
Memory Chart
Comparison Summary
| n | Best | Worst | Ranks |
|---|---|---|---|
| 5 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
| 7 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
| 9 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
| 11 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
| 13 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
| 15 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
Methods & Notes
- Runtime measured with
time.perf_counter(); each (function, n) pair ran 3 times after 2 warmup iterations. GC was enabled and collected before runs. - Memory peak measured with
tracemallocbackend (tracemallocby default). - Confidence Intervals: T at 95% confidence. T-intervals use standard t critical values; bootstrap uses 2,000 resamples with a fixed seed.
- Reference curves (O(1), O(log n), O(n), O(n log n), plus any custom) were normalized at the largest n to match the average observed runtime scale.